1. Technical Field of the Invention
The present invention relates in general to methods for looking up values stored in a table and, in particular, to a method for searching values stored in a table by breaking the table into subtables.
2. Description of Related Art
The present invention is a method for looking up values in a table. However, because it is difficult to discuss the method of the present invention without a framework, the following description of related art focuses on ATM networks and VPI/VCI look-up tables. It should be noted that the present invention may be applied to looking up other values in an ATM or other networks such as, for example, IP or peer-to-peer networks.
An ATM network is composed of nodes, interfaces, links, and virtual resources, just like other network schemes. There are two types of ATM nodes: network nodes and customer premise nodes. Network nodes are located inside an ATM network, while customer premise nodes are located at the peripheries of an ATM network. Network nodes connect to each other or to customer premise nodes. Customer premise nodes connect to network nodes, to user interfaces, or to other types of networks.
Nodes perform the switching and/or data transport functions within an ATM network. A data interface, or “switch,” is located within each network or customer premise node. On network nodes, this interface is called the network node interface (NNI) and on customer premise nodes this interface is called the user network interface (UNI. UNIs are responsible for transferring data, while NNIs are responsible for both transferring data and providing signaling procedures to operate and control the ATM network.
The NNI and UNI are connected to each other by physical links such as coaxial cables. The physical links are then electronically subdivided into virtual paths and virtual channels. Each physical link can carry multiple virtual paths, and each virtual path can carry multiple virtual channels. In fact, up to 256 virtual paths can be defined for each physical link, and up to 65, 536 virtual channels can be defined within each virtual path.
Each virtual path and each virtual channel can be identified by a specific number. For the virtual path, this number is called the virtual path identifier (VPI); for the virtual channel, this number is called the virtual channel identifier (VCI). When combined, the VPI/VCI numeric identifier points to one and only one virtual channel in one and only one virtual path connected to a particular node. Though unique for a particular node, the VPI/VCI identifier may be used a second (or third, or fourth, etc.) time for other non-interconnected nodes within the same ATM network.
The virtual channels in virtual paths on physical links are used to carry segments of C) user data called cells. Each cell contains a header section and a payload section. The entire cell can carry 53 bytes of information, with the header section carrying 5 bytes of information and the payload section carrying 48 bytes of information. Large blocks of user data are broken down to fit into the data-carrying area of the cell, but the payload section is 48 bytes long, even if the information carried within the payload section takes less than 48 bytes of space.
The header section carries all the instructions a cell needs to travel from its origination location to its destination location. The instructions include, for example, data flow and data transfer information. The instructions also identify which virtual path and which virtual channel the cell must use when traveling from one node to another-i.e., the header stores VPI/VCI information.
An ATM cell travels between nodes of an ATM network using a technique called label swapping. Because of timing, traffic, or congestion, when a cell changes physical links at nodes, the cell may also have to change virtual channels and/or virtual paths. If there is a change in the virtual channel and/or virtual path, the cell's VPI and/or VCI must also be changed so that the cell's VPI and VCI identify the correct virtual path and/or virtual channel carrying the cell.
To change the VPI/VCI stored in a cell, three sets of VPI/VCIs must be used: the actual incoming VPI/VCI stored in the cell, a tabulated incoming VPI/VCI stored in the node's memory, and an outgoing VPI/VCI stored in the node's memory and associated with the tabulated incoming VPI/VCI. When a switch is first initialized, a table is generated containing all the possible incoming VPI/VCIs and all the possible outgoing VPI/VCIs. Further, each tabulated incoming VPI/VCI is matched with an outgoing VPI/VCI. This table is stored in the node's memory. When a cell containing an actual incoming VPI/VCI arrives at the node, the actual incoming VPI/VCI is matched with a tabulated incoming VPI/VCI and a set of actions are performed related to the actual incoming VPI/VCI. The actions include, but are not limited to, swapping the actual incoming VPI/VCI with the outgoing VPI/VCI associated with the tabulated incoming VPI/VCI.
There are three general methods of looking up the actual incoming VPI/VCI, matching, and then performing a set of actions related to the actual incoming VPI/VCI. The first method uses the incoming VPI/VCI itself to address the table. Here, the VPI/VCI is entered into a function that maps the 28 bit value to a smaller value, with the value being smaller than 28. The table then has 2″ entries. Alternatively, the 28 bit value can be split into two or more values which are then used to address different tables.
The second prior art way of looking up the actual incoming VPI/VCI, matching, and then performing an action related to the incoming VPI/VCI (such as replacing it with an outgoing VPI/VCI is to simply search the entire VPI/VCI table. Here, the actual incoming VPI/VCI is compared with various tabulated incoming VPI/VCI values in the table. When the incoming VPI/VCI matches a tabulated incoming VPI/VCI in the table, an algorithm is used to perform an action including, but not limited to, swapping the incoming VPI/VCI with an outgoing VPI/VCI, erasing the incoming VPI/VCI, or counting the incoming or outgoing VPI/VCI.
A significant problem with the above-described methods is that they work well when web traffic is slow. However, the methods limit the number of cells passing through a switch if traffic increases. This is so because a switch has only a limited time—the time it takes for the switch to process the cell—to look up an outgoing VCI/VPI and perform the action needed to be performed. As the number of cells passing through the switch increases, the number of tabulated and outgoing VPI/VCI also increases, thereby making the table larger and larger. The increased number of cells also increases the number of look-ups per time period for both the existing table look-up methods described above. The larger table and the greater number of look-ups all decrease the available time for matching the incoming VPI/VCI with the outgoing VPI/VCI. Thus, the time it takes to look up a corresponding VPI/VCI can bottleneck at the node.
A third way for searching a numeric table solves the bottleneck problem but, at the same time, creates problems for other computing power related issues. The third way for searching table entries compares all the values in the table with the search term simultaneously. Since all the values in the table must be compared at the same time, this third method requires a great deal of hardware/processing power. The hardware/processing power requirement then increases the cost of the ATM switch. Thus, a new method is needed to read a value in a table without increasing the hardware/processing power of the switch and will not be restricted by the amount of traffic at the switch.